#include <stdio.h>
#include <conio.h>
#include <iostream>
#include <algorithm>
#include <limits>
#include <time.h>
using namespace std;

#define Max 100000
void SelectionSort(int a[], int n);
void RandomGenerate(int a[], int n);
int random_in_range (unsigned int min, unsigned int max);

int random_in_range (unsigned int min, unsigned int max)
{
  //Randomize
	int base_random = rand(); /* in [0, RAND_MAX] */
	if (RAND_MAX == base_random) return random_in_range(min, max);
  /* now guaranteed to be in [0, RAND_MAX) */
	int range       = max - min,
      remainder   = RAND_MAX % range,
      bucket      = RAND_MAX / range;
  /* There are range buckets, plus one smaller interval
     within remainder of RAND_MAX */
  if (base_random < RAND_MAX - remainder) {
    return min + base_random/bucket;
  } else {
    return random_in_range (min, max);
  }
}

void RandomGenerate(int a[], int n)
{
	for(int i = 0; i < n; i++)
	{
		a[i] = random_in_range(0, 100);
	}
}

void PrintfArray(int a[], int n)
{
	for(int i = 0; i < n; i++)
	{
		printf("  %d", a[i]);
	}
}

void SelectionSort(int a[], int n)
{
	int i, j, temp ;
	for ( i = 0 ; i < n-1 ; i++ )
	{
		for ( j = i + 1 ; j < n ; j++ )
		{
			if ( a[i] > a[j] )
			{
				temp = a[i] ;
				a[i] = a[j] ;
				a[j] = temp ;
			}
		}
	}
}
int main( )
{
	int a[Max];
	int n = 20;
	int N[100];
	for(int i = 1; i < 20; i++)
	{
		N[i] = 10000*i;
	}
	for(int i = 1; i < 10; i++)
	{
		n = N[i];
		//N[i];
		RandomGenerate(a,n);

		//printf ( "\nStar Sort:") ;
		//PrintfArray(a,n);
		clock_t start = clock();
		SelectionSort(a,n);
		//printf ( "\nEnd Sort:") ;
		printf("N = %d\nTime elapsed: %f\n\n",n, ((double)clock() - start) / CLOCKS_PER_SEC);
		//PrintfArray(a,n);

		getch();
	}
	return 0;
}